home *** CD-ROM | disk | FTP | other *** search
/ HPAVC / HPAVC CD-ROM.iso / KADFILE.ZIP / LZC.C < prev    next >
C/C++ Source or Header  |  1995-03-05  |  8KB  |  294 lines
  1. /**************************************************************
  2.     LZARI.C -- A Data Compression Program
  3.     (tab = 4 spaces)
  4. ***************************************************************
  5.     4/7/1989 Haruhiko Okumura
  6.     Use, distribute, and modify this program freely.
  7.     Please send me your improved versions.
  8.         PC-VAN        SCIENCE
  9.         NIFTY-Serve    PAF01022
  10.         CompuServe    74050,1022
  11. **************************************************************/
  12. /****************************************************************************/
  13. /* LZC compression system                                                       */
  14. /* Functions under DOS4Gw and PmodeW                                        */
  15. /*--------------------------------------------------------------------------*/
  16. /* Modified by Kodiak of The Apollo Project                                    */
  17. /* AKA Charles Jones                                                        */
  18. /*     1122 s 32nd St #2                                                    */
  19. /*     Omaha, NE 68105                                                      */
  20. /*     (402)-346-8974                                                       */
  21. /*                                                                          */
  22. /* Email: CAD@UnOmaha.edu                                                   */
  23. /* IRC  : #Coders                                                           */
  24. /*                                                                          */
  25. /****************************************************************************/
  26. /* I take no credit for this compresion system. I simply modifed the        */
  27. /* original code supplied by Haruhiko Okumura.  This code only DECODES      */
  28. /* from either disk files or memory.  I included this system to show how    */
  29. /* easy compression is to add to your projects.                             */
  30. /****************************************************************************/
  31.  
  32. #include <stdio.h>
  33. #include <stdlib.h>
  34. #include <string.h>
  35. #include <ctype.h>
  36.  
  37.  
  38. extern FILE *kadfile;
  39.  
  40. unsigned char *targetarray;
  41. long int targetpointer;
  42.  
  43. /********** Bit I/O **********/
  44. unsigned long int  textsize = 0, printcount = 0;
  45.  
  46. /********** LZSS with multiple binary trees **********/
  47.  
  48. #define N         4096   /* size of ring buffer */
  49. #define F         60     /* upper limit for match_length */
  50. #define THRESHOLD 2      /* encode string into position and length
  51.                  if match_length is greater than this */
  52.  
  53. unsigned char  text_buf[N + F - 1];     /* ring buffer of size N,
  54.                with extra F-1 bytes to facilitate string comparison */
  55.  
  56.  
  57. /********** Arithmetic Compression **********/
  58.  
  59. /*  If you are not familiar with arithmetic compression, you should read
  60.         I. E. Witten, R. M. Neal, and J. G. Cleary,
  61.             Communications of the ACM, Vol. 30, pp. 520-540 (1987),
  62.     from which much have been borrowed.  */
  63.  
  64. #define M   15
  65.  
  66. /*      Q1 (= 2 to the M) must be sufficiently large, but not so
  67.     large as the unsigned long 4 * Q1 * (Q1 - 1) overflows.  */
  68.  
  69. #define Q1  (1UL << M)
  70. #define Q2  (2 * Q1)
  71. #define Q3  (3 * Q1)
  72. #define Q4  (4 * Q1)
  73. #define MAX_CUM (Q1 - 1)
  74.  
  75. #define N_CHAR  (256 - THRESHOLD + F)
  76.     /* character code = 0, 1, ..., N_CHAR - 1 */
  77.  
  78. unsigned long int  low = 0, high = Q4, value = 0;
  79. int  shifts = 0;  /* counts for magnifying low and high around Q2 */
  80. int  char_to_sym[N_CHAR], sym_to_char[N_CHAR + 1];
  81. unsigned int
  82.     sym_freq[N_CHAR + 1],  /* frequency for symbols */
  83.     sym_cum[N_CHAR + 1],   /* cumulative freq for symbols */
  84.     position_cum[N + 1];   /* cumulative freq for positions */
  85.  
  86.  
  87. char *sourcearray;
  88. long int  sourcepointer;
  89. int (*getinputchar)(FILE *filename);                    /* pointer to primary irq */
  90.  
  91.  
  92. void putcs(unsigned char c)
  93. {
  94.     targetarray[targetpointer++] = c;
  95. }
  96.  
  97. int getcs(FILE *filename)
  98. {
  99.    char c;
  100.    c = sourcearray[sourcepointer++];
  101.    return(c);
  102. }
  103.  
  104.  
  105. int GetBit(void)  /* Get one bit (0 or 1) */
  106. {
  107.     static unsigned int  buffer, mask = 0;
  108.  
  109.     if ((mask >>= 1) == 0) {
  110.         buffer = getinputchar(kadfile);  mask = 128;
  111.     }
  112.     return ((buffer & mask) != 0);
  113. }
  114.  
  115. void StartModel(void)  /* Initialize model */
  116. {
  117.     int ch, sym, i;
  118.  
  119.     sym_cum[N_CHAR] = 0;
  120.     for (sym = N_CHAR; sym >= 1; sym--) {
  121.         ch = sym - 1;
  122.         char_to_sym[ch] = sym;  sym_to_char[sym] = ch;
  123.         sym_freq[sym] = 1;
  124.         sym_cum[sym - 1] = sym_cum[sym] + sym_freq[sym];
  125.     }
  126.     sym_freq[0] = 0;  /* sentinel (!= sym_freq[1]) */
  127.     position_cum[N] = 0;
  128.     for (i = N; i >= 1; i--)
  129.         position_cum[i - 1] = position_cum[i] + 10000 / (i + 200);
  130.             /* empirical distribution function (quite tentative) */
  131.             /* Please devise a better mechanism! */
  132. }
  133.  
  134. void UpdateModel(int sym)
  135. {
  136.     int i, c, ch_i, ch_sym;
  137.  
  138.     if (sym_cum[0] >= MAX_CUM) {
  139.         c = 0;
  140.         for (i = N_CHAR; i > 0; i--) {
  141.             sym_cum[i] = c;
  142.             c += (sym_freq[i] = (sym_freq[i] + 1) >> 1);
  143.         }
  144.         sym_cum[0] = c;
  145.     }
  146.     for (i = sym; sym_freq[i] == sym_freq[i - 1]; i--) ;
  147.     if (i < sym) {
  148.         ch_i = sym_to_char[i];    ch_sym = sym_to_char[sym];
  149.         sym_to_char[i] = ch_sym;  sym_to_char[sym] = ch_i;
  150.         char_to_sym[ch_i] = sym;  char_to_sym[ch_sym] = i;
  151.     }
  152.     sym_freq[i]++;
  153.     while (--i >= 0) sym_cum[i]++;
  154. }
  155.  
  156. int BinarySearchSym(unsigned int x)
  157.     /* 1      if x >= sym_cum[1],
  158.        N_CHAR if sym_cum[N_CHAR] > x,
  159.        i such that sym_cum[i - 1] > x >= sym_cum[i] otherwise */
  160. {
  161.     int i, j, k;
  162.  
  163.     i = 1;  j = N_CHAR;
  164.     while (i < j) {
  165.         k = (i + j) / 2;
  166.         if (sym_cum[k] > x) i = k + 1;  else j = k;
  167.     }
  168.     return i;
  169. }
  170.  
  171. int BinarySearchPos(unsigned int x)
  172.     /* 0 if x >= position_cum[1],
  173.        N - 1 if position_cum[N] > x,
  174.        i such that position_cum[i] > x >= position_cum[i + 1] otherwise */
  175. {
  176.     int i, j, k;
  177.  
  178.     i = 1;  j = N;
  179.     while (i < j) {
  180.         k = (i + j) / 2;
  181.         if (position_cum[k] > x) i = k + 1;  else j = k;
  182.     }
  183.     return i - 1;
  184. }
  185.  
  186. void StartDecode(void)
  187. {
  188.     int i;
  189.  
  190.     for (i = 0; i < M + 2; i++)
  191.         value = 2 * value + GetBit();
  192. }
  193.  
  194. int DecodeChar(void)
  195. {
  196.     int      sym, ch;
  197.     unsigned long int  range;
  198.  
  199.     range = high - low;
  200.     sym = BinarySearchSym((unsigned int)
  201.         (((value - low + 1) * sym_cum[0] - 1) / range));
  202.     high = low + (range * sym_cum[sym - 1]) / sym_cum[0];
  203.     low +=       (range * sym_cum[sym    ]) / sym_cum[0];
  204.     for ( ; ; ) {
  205.         if (low >= Q2) {
  206.             value -= Q2;  low -= Q2;  high -= Q2;
  207.         } else if (low >= Q1 && high <= Q3) {
  208.             value -= Q1;  low -= Q1;  high -= Q1;
  209.         } else if (high > Q2) break;
  210.         low += low;  high += high;
  211.         value = 2 * value + GetBit();
  212.     }
  213.     ch = sym_to_char[sym];
  214.     UpdateModel(sym);
  215.     return ch;
  216. }
  217.  
  218. int DecodePosition(void)
  219. {
  220.     int position;
  221.     unsigned long int  range;
  222.  
  223.     range = high - low;
  224.     position = BinarySearchPos((unsigned int)
  225.         (((value - low + 1) * position_cum[0] - 1) / range));
  226.     high = low + (range * position_cum[position    ]) / position_cum[0];
  227.     low +=       (range * position_cum[position + 1]) / position_cum[0];
  228.     for ( ; ; ) {
  229.         if (low >= Q2) {
  230.             value -= Q2;  low -= Q2;  high -= Q2;
  231.         } else if (low >= Q1 && high <= Q3) {
  232.             value -= Q1;  low -= Q1;  high -= Q1;
  233.         } else if (high > Q2) break;
  234.         low += low;  high += high;
  235.         value = 2 * value + GetBit();
  236.     }
  237.     return position;
  238. }
  239.  
  240. /********** Encode and Decode **********/
  241. int Decode(void)
  242. {
  243.     int  i, j, k, r, c;
  244.     unsigned long int  count;
  245.  
  246.     if (fread(&textsize, sizeof textsize, 1, kadfile) != 1)
  247.             return(8);
  248.  
  249.         if (sourcearray != NULL)
  250.             fread(sourcearray, textsize, 1, kadfile);
  251.  
  252.     if (textsize == 0) return(7);
  253.     StartDecode();  StartModel();
  254.     for (i = 0; i < N - F; i++) text_buf[i] = ' ';
  255.     r = N - F;
  256.     for (count = 0; count < textsize; ) {
  257.         c = DecodeChar();
  258.         if (c < 256) {
  259.             putcs(c);  text_buf[r++] = c;
  260.             r &= (N - 1);  count++;
  261.         } else {
  262.             i = (r - DecodePosition() - 1) & (N - 1);
  263.             j = c - 255 + THRESHOLD;
  264.             for (k = 0; k < j; k++) {
  265.                 c = text_buf[(i + k) & (N - 1)];
  266.                 putcs(c);  text_buf[r++] = c;
  267.                 r &= (N - 1);  count++;
  268.             }
  269.         }
  270.     }
  271.     return(0);
  272. }
  273.  
  274. int decompress(unsigned char *where, int filesize)
  275. {
  276.     int temp;
  277.  
  278.         sourcepointer = 0;
  279.         sourcearray = (char *) malloc(filesize);
  280.  
  281.         getinputchar = getc;
  282.  
  283.         if (sourcearray != NULL)
  284.             getinputchar = getcs;
  285.  
  286.     targetarray = where;
  287.     targetpointer = 0;
  288.  
  289.         temp = Decode();
  290.  
  291.         free ((void *) sourcearray);
  292.     return(temp);
  293. }
  294.